#pragma once
#include <iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLtreenode
{
	pair<K, V> as;
	AVLtreenode<K, V>* _parent;
	AVLtreenode<K, V>* _left;
	AVLtreenode<K, V>* _right;
	int _bf;
	AVLtreenode(const pair<K,V>& t)
		:as(t)
		,_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_bf(0)
	{

	}

};
template<class K, class V>
class AVLtree
{
	typedef AVLtreenode<K,V> node;
public:
	bool insert(const pair<K,V>& t)
	{
		if (_root == nullptr)
		{
			_root = new node(t);
			return true;
		}
		node* cur = _root;
		node* parent = nullptr;
		while (cur)
		{
			if (cur->as.first < t.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->as.first > t.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new node(t);
		if (parent->as.first < t.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent)
		{
			if (cur==parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if(parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf==-2||parent->_bf==1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 || parent->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
	void RotateR(node* parent)
	{
		node* cur = parent->_left;
		node* curR = cur->_right;
		parent->_left = curR;
		if (curR)
			curR->_parent = parent;
		node* Gparent = parent->_parent;
		cur->_right = parent;
		parent->_parent = cur;
		if ( parent==_root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (Gparent->_left == parent)
				Gparent->_left = cur;
			else
				Gparent->_right = cur;
			cur->_parent = Gparent;
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}
	
	void RotateL(node* parent)
	{
		node* cur = parent->_right;
		node* curL = cur->_left;
		parent->_right = curL;
		cur->_left = parent;
		node* Gparent = parent->_parent;
		parent->_parent = cur;
		if (curL)
		{
			curL->_parent = parent;
		}
		if (_root == parent)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			cur->_parent = Gparent;
			if (Gparent->_left == parent)
				Gparent->_left = cur;
			else
				Gparent->_right = cur;
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}
	void RotateLR(node* parent)
	{
		node* cur = parent->_left;
		node* curR = cur->_right;
		int bf = curR->_bf;
		RotateL(cur);
		RotateR(parent);
		if (bf==-1)
		{
			curR->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			curR->_bf = 0;
			cur->_bf = -1;
			parent->_bf = 0;
		}
		else if(bf==0)
		{
			curR->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}
	void RotateRL(node* parent)
	{
		node* cur = parent->_right;
		node* curL = cur->_left;
		int bf = curL->_bf;
		RotateR(cur);
		RotateL(parent);
		if (bf == -1)
		{
			curL->_bf = 0;
			cur->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			curL->_bf = 0;
			cur->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == 0)
		{
			curL->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}

	node* Find(const K& key)
	{
		node* cur = _root;
		while (cur)
		{
			if (cur->as.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->as.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}
private:
	void _InOrder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->as.first << ":" << root->as.second << endl;
		_InOrder(root->_right);
	}
	int _Height(node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftheight = _Height(root->_left);
		int rightheight = _Height(root->_right);
		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	}
	int _Size(node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}
	bool _IsBalanceTree(node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int left = _Height(root->_left);
		int right = _Height(root->_right);
		if (abs(right - left)>=2)
		{
			return false;
		}
		if (root->_bf != right - left)
		{
			return false;
		}
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
private:
	node* _root = nullptr;
};
